#include "StdAfx.h"
#include "PrefixSorting.h"
#include <assert.h>


CPrefixSorting::CPrefixSorting(void)
{
	m_nCakeCnt = 0;
	m_nMaxSwap = 0;
}

CPrefixSorting::~CPrefixSorting(void)
{
}

// Initialize arrays information.
// @param
// pCakeArray	Store cake index array.
// nCakeCnt		Cake number.
//
void CPrefixSorting::Init(int* pCakeArray, int nCakeCnt)
{
	assert(pCakeArray != NULL);
	assert(nCakeCnt > 0);

	m_nCakeCnt = nCakeCnt;

	// Initialize cake array.
	m_CakeArray = new int[m_nCakeCnt];
	assert(m_CakeArray != NULL);
	for (int i = 0; i < m_nCakeCnt; i++)
	{
		m_CakeArray[i] = pCakeArray[i];
	}

	// Set max swap info.
	m_nMaxSwap = UpperBound(m_nCakeCnt);

	// Initialize swap result.
	m_SwapArray = new int[m_nMaxSwap];
	assert(m_SwapArray != NULL);

	// Initialize reverse swap result.
	m_ReverseCakeArray = new int[m_nCakeCnt];
	assert(m_ReverseCakeArray != NULL);
	for (int i = 0; i < m_nCakeCnt; i++)
	{
		m_ReverseCakeArray[i] = m_CakeArray[i];
	}
	m_ReverseCakeArraySwap = new int[m_nMaxSwap];
}

//
// Find current revert upper bound.
//
int CPrefixSorting::UpperBound(int nCakeCnt)
{
	return nCakeCnt * 2;
}

//
// Find current revert lower bound.
//
int CPrefixSorting::LowerBound(int* pCakeArray, int nCakeCnt)
{
	int ret = 0;

	// Get mix swap count according to current array's sorting information.
	for (int i = 1; i < nCakeCnt ; i++)
	{
		// Determine if the location adjacent of the cake is size sorting adjacent.
		int t = pCakeArray[i] - pCakeArray[i-1];
		if (t == 1 || t == -1)
		{
		} 
		else
		{
			ret++;
		}
	}

	return ret;
}

//
// Main sort function.
//
void CPrefixSorting::Search(int step)
{
	m_nSearch++;

	// Estimate min swap count of searching.
	int nEstimate = LowerBound(m_ReverseCakeArray, m_nCakeCnt);
	if (step + nEstimate > m_nMaxSwap)
	{
		return;
	}

	// If is sorted, the reversion completed, output the result.
	if (IsSorted(m_ReverseCakeArray, m_nCakeCnt))
	{
		if (step < m_nMaxSwap)
		{
			m_nMaxSwap = step;
			for (int i = 0; i < m_nMaxSwap ; i++)
			{
				m_SwapArray[i] = m_ReverseCakeArraySwap[i];
			}
		}

		return;
	}

	// Recursive revert.
	for (int i = 1; i < m_nCakeCnt ; i++)
	{
		Revert(0, i);
		m_ReverseCakeArraySwap[step] = i;
		Search(step + 1);
		Revert(0, i);
	}
}

//
// Is sorted.
//
bool CPrefixSorting::IsSorted(int* pCakeArray, int nCakeCnt)
{
	for (int i = 1; i < nCakeCnt ; i++)
	{
		if (pCakeArray[i-1] > pCakeArray[i])
		{
			return false;
		}
	}
	return true;
}

//
// Revert cake.
//
void CPrefixSorting::Revert(int nBegin, int nEnd)
{
	assert(nEnd > nBegin);

	int i, j, t;

	// Revert cake.
	for (i = nBegin, j = nEnd; i < j; i++, j--)
	{
		t = m_ReverseCakeArray[i];
		m_ReverseCakeArray[i] = m_ReverseCakeArray[j];
		m_ReverseCakeArray[j] = t;
	}
}

//
// Calculate cake revert information.
// @param
// pCakeArray	Store cake index array.
// nCakeCnt		Cake number.
//
void CPrefixSorting::Run(int* pCakeArray, int nCakeCnt)
{
	Init(pCakeArray, nCakeCnt);

	m_nSearch = 0;
	Search(0);
}

//
// Output cakes' revert count.
//
void CPrefixSorting::Output()
{
	printf("\nOutput: \n");
	for (int i = 0; i < m_nMaxSwap ; i++)
	{
		printf("%d ", m_SwapArray[i]);
	}

	printf("\n|Search Time| : %d\n", m_nSearch);
	printf("Total Swap times = %d\n", m_nMaxSwap);
}